<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>代码仓库 | whoway</title>
    <meta name="description" content="Personal Blog Website">
    <link rel="icon" href="/images/photo.jpg">
  <link rel="manifest" href="/images/photo.jpg">
  <link rel="apple-touch-icon" href="/images/photo.jpg">
  <meta http-quiv="pragma" cotent="no-cache">
  <meta http-quiv="pragma" cotent="no-cache,must-revalidate">
  <meta http-quiv="expires" cotent="0">
    
    <link rel="preload" href="/assets/css/0.styles.0dbae9ec.css" as="style"><link rel="preload" href="/assets/js/app.c70e21ad.js" as="script"><link rel="preload" href="/assets/js/9.3813842d.js" as="script"><link rel="prefetch" href="/assets/js/10.15222a53.js"><link rel="prefetch" href="/assets/js/100.7e0e5a86.js"><link rel="prefetch" href="/assets/js/101.efd59f25.js"><link rel="prefetch" href="/assets/js/102.dfbdc06c.js"><link rel="prefetch" href="/assets/js/103.d3ab2109.js"><link rel="prefetch" href="/assets/js/104.117957ef.js"><link rel="prefetch" href="/assets/js/105.046e8ff3.js"><link rel="prefetch" href="/assets/js/106.aebdc17d.js"><link rel="prefetch" href="/assets/js/107.248733c2.js"><link rel="prefetch" href="/assets/js/108.a2fecadc.js"><link rel="prefetch" href="/assets/js/109.35196857.js"><link rel="prefetch" href="/assets/js/11.770642f2.js"><link rel="prefetch" href="/assets/js/110.cf3d973c.js"><link rel="prefetch" href="/assets/js/111.f985889a.js"><link rel="prefetch" href="/assets/js/112.ad614f41.js"><link rel="prefetch" href="/assets/js/113.f666653c.js"><link rel="prefetch" href="/assets/js/114.c6c3f384.js"><link rel="prefetch" href="/assets/js/115.e51d3c2f.js"><link rel="prefetch" href="/assets/js/116.4f4b39f5.js"><link rel="prefetch" href="/assets/js/117.99352e11.js"><link rel="prefetch" href="/assets/js/118.c6ae6572.js"><link rel="prefetch" href="/assets/js/119.4ccbe778.js"><link rel="prefetch" href="/assets/js/12.042a92ff.js"><link rel="prefetch" href="/assets/js/120.edda1c4f.js"><link rel="prefetch" href="/assets/js/121.30a638ed.js"><link rel="prefetch" href="/assets/js/122.6efcefb1.js"><link rel="prefetch" href="/assets/js/123.91e6665b.js"><link rel="prefetch" href="/assets/js/124.f27e3d7e.js"><link rel="prefetch" href="/assets/js/125.c75712d5.js"><link rel="prefetch" href="/assets/js/126.ed756cce.js"><link rel="prefetch" href="/assets/js/127.2f06c74c.js"><link rel="prefetch" href="/assets/js/128.d5f6f30e.js"><link rel="prefetch" href="/assets/js/129.508b7eed.js"><link rel="prefetch" href="/assets/js/13.b5280c37.js"><link rel="prefetch" href="/assets/js/130.dc05f9aa.js"><link rel="prefetch" href="/assets/js/131.e0ba69b1.js"><link rel="prefetch" href="/assets/js/132.d79bcaa4.js"><link rel="prefetch" href="/assets/js/133.34acc01a.js"><link rel="prefetch" href="/assets/js/134.dabf64d5.js"><link rel="prefetch" href="/assets/js/135.ad90c915.js"><link rel="prefetch" href="/assets/js/136.dbb0074f.js"><link rel="prefetch" href="/assets/js/137.284ad365.js"><link rel="prefetch" href="/assets/js/138.a4b6856f.js"><link rel="prefetch" href="/assets/js/139.c9c1e20f.js"><link rel="prefetch" href="/assets/js/14.df02ba38.js"><link rel="prefetch" href="/assets/js/140.8b0a9269.js"><link rel="prefetch" href="/assets/js/141.9c7759c5.js"><link rel="prefetch" href="/assets/js/142.a4201a82.js"><link rel="prefetch" href="/assets/js/143.d7da6e8c.js"><link rel="prefetch" href="/assets/js/144.5e48e65d.js"><link rel="prefetch" href="/assets/js/145.a0e2633c.js"><link rel="prefetch" href="/assets/js/146.3c775f9b.js"><link rel="prefetch" href="/assets/js/147.22add89a.js"><link rel="prefetch" href="/assets/js/148.cfde1009.js"><link rel="prefetch" href="/assets/js/149.ffc835b5.js"><link rel="prefetch" href="/assets/js/15.fbdfc4ee.js"><link rel="prefetch" href="/assets/js/150.406c4b20.js"><link rel="prefetch" href="/assets/js/151.b2040eea.js"><link rel="prefetch" href="/assets/js/152.7bc65661.js"><link rel="prefetch" href="/assets/js/153.1d7c65e3.js"><link rel="prefetch" href="/assets/js/154.1309de49.js"><link rel="prefetch" href="/assets/js/155.81d3ee1f.js"><link rel="prefetch" href="/assets/js/156.154a4ef2.js"><link rel="prefetch" href="/assets/js/16.e5eb6147.js"><link rel="prefetch" href="/assets/js/17.57853c4a.js"><link rel="prefetch" href="/assets/js/18.cb9d7518.js"><link rel="prefetch" href="/assets/js/19.f354dc47.js"><link rel="prefetch" href="/assets/js/2.570d8a23.js"><link rel="prefetch" href="/assets/js/20.b5af7fad.js"><link rel="prefetch" href="/assets/js/21.0b1928fe.js"><link rel="prefetch" href="/assets/js/22.f78666de.js"><link rel="prefetch" href="/assets/js/23.29c3f366.js"><link rel="prefetch" href="/assets/js/24.6f596516.js"><link rel="prefetch" href="/assets/js/25.14067b60.js"><link rel="prefetch" href="/assets/js/26.74ba4989.js"><link rel="prefetch" href="/assets/js/27.13d60edd.js"><link rel="prefetch" href="/assets/js/28.9523cb32.js"><link rel="prefetch" href="/assets/js/29.8ec842e9.js"><link rel="prefetch" href="/assets/js/3.3fb3d2e0.js"><link rel="prefetch" href="/assets/js/30.805597a8.js"><link rel="prefetch" href="/assets/js/31.831b195d.js"><link rel="prefetch" href="/assets/js/32.063c672d.js"><link rel="prefetch" href="/assets/js/33.6d93fac3.js"><link rel="prefetch" href="/assets/js/34.56e8263c.js"><link rel="prefetch" href="/assets/js/35.dbe688bb.js"><link rel="prefetch" href="/assets/js/36.dc5af2c1.js"><link rel="prefetch" href="/assets/js/37.0a7494f6.js"><link rel="prefetch" href="/assets/js/38.fe4fc171.js"><link rel="prefetch" href="/assets/js/39.f5ed5e92.js"><link rel="prefetch" href="/assets/js/4.2c405ec8.js"><link rel="prefetch" href="/assets/js/40.fe7e2714.js"><link rel="prefetch" href="/assets/js/41.30b0811d.js"><link rel="prefetch" href="/assets/js/42.76f52d62.js"><link rel="prefetch" href="/assets/js/43.e7bb0817.js"><link rel="prefetch" href="/assets/js/44.ead0e883.js"><link rel="prefetch" href="/assets/js/45.235df046.js"><link rel="prefetch" href="/assets/js/46.5f09e829.js"><link rel="prefetch" href="/assets/js/47.67116354.js"><link rel="prefetch" href="/assets/js/48.31f34543.js"><link rel="prefetch" href="/assets/js/49.10b5ebba.js"><link rel="prefetch" href="/assets/js/5.6f47322c.js"><link rel="prefetch" href="/assets/js/50.c0f0b7f1.js"><link rel="prefetch" href="/assets/js/51.5143f3bf.js"><link rel="prefetch" href="/assets/js/52.eeddfd48.js"><link rel="prefetch" href="/assets/js/53.eb790db5.js"><link rel="prefetch" href="/assets/js/54.8fe5421c.js"><link rel="prefetch" href="/assets/js/55.d8f9004b.js"><link rel="prefetch" href="/assets/js/56.62ac9b92.js"><link rel="prefetch" href="/assets/js/57.a9caec0d.js"><link rel="prefetch" href="/assets/js/58.f93fc522.js"><link rel="prefetch" href="/assets/js/59.a81a03aa.js"><link rel="prefetch" href="/assets/js/6.8c2ea393.js"><link rel="prefetch" href="/assets/js/60.ab782775.js"><link rel="prefetch" href="/assets/js/61.6dd12daf.js"><link rel="prefetch" href="/assets/js/62.76f4b01f.js"><link rel="prefetch" href="/assets/js/63.6f8a4742.js"><link rel="prefetch" href="/assets/js/64.6f8bb1fa.js"><link rel="prefetch" href="/assets/js/65.4120a44b.js"><link rel="prefetch" href="/assets/js/66.360c2d2b.js"><link rel="prefetch" href="/assets/js/67.26f84d32.js"><link rel="prefetch" href="/assets/js/68.68f45e5e.js"><link rel="prefetch" href="/assets/js/69.e311eb56.js"><link rel="prefetch" href="/assets/js/7.6762b2d7.js"><link rel="prefetch" href="/assets/js/70.cea82674.js"><link rel="prefetch" href="/assets/js/71.783ddcf7.js"><link rel="prefetch" href="/assets/js/72.e5467385.js"><link rel="prefetch" href="/assets/js/73.b8fb681b.js"><link rel="prefetch" href="/assets/js/74.1bae37db.js"><link rel="prefetch" href="/assets/js/75.024387e5.js"><link rel="prefetch" href="/assets/js/76.a8e53010.js"><link rel="prefetch" href="/assets/js/77.8c55500a.js"><link rel="prefetch" href="/assets/js/78.7ce90bf5.js"><link rel="prefetch" href="/assets/js/79.ef71713f.js"><link rel="prefetch" href="/assets/js/8.788a6364.js"><link rel="prefetch" href="/assets/js/80.acad589d.js"><link rel="prefetch" href="/assets/js/81.02670d10.js"><link rel="prefetch" href="/assets/js/82.53b7b1ac.js"><link rel="prefetch" href="/assets/js/83.99eb8581.js"><link rel="prefetch" href="/assets/js/84.d1535ce3.js"><link rel="prefetch" href="/assets/js/85.fe2b7de9.js"><link rel="prefetch" href="/assets/js/86.41850272.js"><link rel="prefetch" href="/assets/js/87.1cdc6df9.js"><link rel="prefetch" href="/assets/js/88.01bf3461.js"><link rel="prefetch" href="/assets/js/89.17c69819.js"><link rel="prefetch" href="/assets/js/90.f6ae7e35.js"><link rel="prefetch" href="/assets/js/91.507bc284.js"><link rel="prefetch" href="/assets/js/92.90551782.js"><link rel="prefetch" href="/assets/js/93.dc442d78.js"><link rel="prefetch" href="/assets/js/94.315f4e94.js"><link rel="prefetch" href="/assets/js/95.ccd6c6bf.js"><link rel="prefetch" href="/assets/js/96.0c6d89d0.js"><link rel="prefetch" href="/assets/js/97.1a9f10a9.js"><link rel="prefetch" href="/assets/js/98.43be3caa.js"><link rel="prefetch" href="/assets/js/99.54c8207b.js">
    <link rel="stylesheet" href="/assets/css/0.styles.0dbae9ec.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">whoway</span></a> <div class="links" style="max-width:nullpx;"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" aria-current="page" class="nav-link router-link-exact-active router-link-active">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <div class="sidebar"><nav class="nav-links"><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🎓Coding</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/00.Coding/TheBeautyOfProgramming/" class="nav-link">🔖编程之美题解</a></li><li class="dropdown-item"><!----> <a href="/00.Coding/CodeWarehouse/" aria-current="page" class="nav-link router-link-exact-active router-link-active">🔖代码意识流</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">🚀语言</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/01.Language/Overview/" class="nav-link">🔖概述</a></li><li class="dropdown-item"><!----> <a href="/01.Language/C/" class="nav-link">⭐️C</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Cpp/" class="nav-link">🚀C++</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Java/" class="nav-link">☕️Java</a></li><li class="dropdown-item"><!----> <a href="/01.Language/Python/" class="nav-link">🧩Python3</a></li></ul></div></div><div class="nav-item"><a href="/02.Hardware/" class="nav-link">✔️硬件基础</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⭐️软件基础</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/03.Software/01.DataStructureAndAlgorithm/" class="nav-link">🐾数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/03.Software/02.OS/" class="nav-link">💻操作系统</a></li><li class="dropdown-item"><!----> <a href="/03.Software/03.Net/" class="nav-link">☁️计算机网络</a></li><li class="dropdown-item"><!----> <a href="/03.Software/04.SE/" class="nav-link">✅软件工程</a></li></ul></div></div><div class="nav-item"><a href="/04.Database/" class="nav-link">🎨数据库</a></div><div class="nav-item"><a href="/05.Engineer/" class="nav-link">🔖学术/工程</a></div><div class="nav-item"><div class="dropdown-wrapper"><a class="dropdown-title"><span class="title">⚙️工具</span> <span class="arrow right"></span></a> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/06.Tools/01.employment/" class="nav-link">🔖求职</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/02.efficiency/" class="nav-link">🚀效能</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/03.windows/" class="nav-link">⚙️Windows</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/04.design/" class="nav-link">🧩设计</a></li><li class="dropdown-item"><!----> <a href="/06.Tools/05.linux/" class="nav-link">🐉Linux</a></li></ul></div></div><div class="nav-item"><a href="https://github.com/whoway" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></div> <!----></nav>  <ul class="sidebar-links"><li><div class="sidebar-group first"><p class="sidebar-heading open"><span>代码仓库</span> <!----></p> <ul class="sidebar-group-items"><li><a href="/00.Coding/CodeWarehouse/#传送门" class="sidebar-link">传送门</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#目录" class="sidebar-link">目录</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#_01-在旋转过的有序数组中寻找目标值" class="sidebar-link">01.在旋转过的有序数组中寻找目标值</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#_02-将字符串转化为整数" class="sidebar-link">02.将字符串转化为整数</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#_03-字符串分割" class="sidebar-link">03.字符串分割</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/00.Coding/CodeWarehouse/#面试题整理" class="sidebar-link">面试题整理</a></li><li class="sidebar-sub-header"><a href="/00.Coding/CodeWarehouse/#操作系统" class="sidebar-link">操作系统</a></li><li class="sidebar-sub-header"><a href="/00.Coding/CodeWarehouse/#数据结构和算法" class="sidebar-link">数据结构和算法</a></li></ul></li><li><a href="/00.Coding/CodeWarehouse/#_04-kmp" class="sidebar-link">04.KMP</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#_05-⭐️二叉树中的最大路径和『树形dp』" class="sidebar-link">05.⭐️二叉树中的最大路径和『树形dp』</a><ul class="sidebar-sub-headers"></ul></li><li><a href="/00.Coding/CodeWarehouse/#_06-最接近的三数之和" class="sidebar-link">06.最接近的三数之和</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/00.Coding/CodeWarehouse/#同类问题" class="sidebar-link">同类问题</a></li></ul></li><li><a href="/00.Coding/CodeWarehouse/#_07-盛最多水的容器" class="sidebar-link">07.盛最多水的容器</a><ul class="sidebar-sub-headers"></ul></li></ul></div></li></ul> </div> <div class="page"> <div class="content"><h1 id="代码仓库"><a href="#代码仓库" class="header-anchor">#</a> 代码仓库</h1> <ul><li>codetop<a href="https://codetop.cc/home" target="_blank" rel="noopener noreferrer">刷题站点<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a> <ul><li>分公司</li> <li>分部门</li> <li>分base</li></ul></li></ul> <h2 id="传送门"><a href="#传送门" class="header-anchor">#</a> 传送门</h2> <ul><li>part01.<a href="/00.Coding/CodeWarehouse/part01.国内版Leetcode踩坑记录.html">国内版Leetcode踩坑记录</a></li> <li>part02.<a href="/00.Coding/CodeWarehouse/part02.牛客网各个错误的解释.html">牛客网各个错误的解释</a></li></ul> <h2 id="目录"><a href="#目录" class="header-anchor">#</a> 目录</h2> <p>[TOC]</p> <h2 id="_01-在旋转过的有序数组中寻找目标值"><a href="#_01-在旋转过的有序数组中寻找目标值" class="header-anchor">#</a> 01.在旋转过的有序数组中寻找目标值</h2> <ul><li>NC48<a href="https://www.nowcoder.com/practice/87c0e7abcbda41e7963660fa7d020995?tpId=117&&tqId=37744&&companyId=665&rp=1&ru=/company/home/code/665&qru=/ta/job-code-high/question-ranking" target="_blank" rel="noopener noreferrer">在旋转过的有序数组中寻找目标值<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>LeetCode<a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array/" target="_blank" rel="noopener noreferrer">33. 搜索旋转排序数组<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <p>『卡过』</p> <blockquote><p>但凡是从有序序列中找某个数，我们第一反应应该是「二分』</p></blockquote> <ul><li>这道题是一个原本有序的数组在某个点上进行了旋转，其实就是将原本一段升序的数组分为了两段</li> <li>这道题其实是要我们明确「二分」的本质是什么
<ul><li>「二分」不是单纯指从有序数组中快速找某个数，这只是「二分」的一个应用</li> <li><font style="background:yellow;">「二分」的本质是两段性，并非单调性</font>。只要一段满足某个性质，另外一段不满足某个性质，就可以用「二分」</li></ul></li> <li>参考自作者：<code>AC_OIer</code>
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/shua-chuan-lc-yan-ge-ologn100yi-qi-kan-q-xifo/</li></ul> <h4 id="_1-1-思路—分情况讨论"><a href="#_1-1-思路—分情况讨论" class="header-anchor">#</a> 1.1.思路—分情况讨论</h4> <ul><li>情况1</li></ul> <img src="https://uploadfiles.nowcoder.com/images/20210629/258551806_1624956593632/26C095B637DF7BAB1A260905015F8ED2"> <ul><li><p>情况2
<img src="https://uploadfiles.nowcoder.com/images/20210629/258551806_1624956801301/46E1ECA1FE62CD44A9A53CE525447C39"></p></li> <li><p>情况3</p></li> <li><p>发现，情况3可以被情况1和2所顺路讨论，代码见后边</p></li></ul> <img src="https://uploadfiles.nowcoder.com/images/20210629/258551806_1624956925786/EC8C6E3375666B3A2EBFAC1045D79F9A"> <h4 id="_1-2-坑点"><a href="#_1-2-坑点" class="header-anchor">#</a> 1.2.坑点</h4> <p>比如：1,3寻找3
那么，nums[Right]可能和target相同，见代码中标记的易错点</p> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token comment">/**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */</span>
    <span class="token keyword">int</span> <span class="token function">search</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token comment">// write code here</span>
        
        <span class="token keyword">int</span> Len<span class="token operator">=</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token operator">==</span>Len <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">1</span><span class="token operator">==</span>Len <span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>target<span class="token operator">==</span>nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">?</span> <span class="token number">0</span> <span class="token operator">:</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        
        <span class="token comment">//[Left,Right】</span>
        <span class="token comment">//不能用[Left,Right)，原因是，左右2个点，我都需要使用</span>
        <span class="token keyword">int</span> Left<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>Right<span class="token operator">=</span>Len<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        
        <span class="token comment">//因为是[left,Right]，然后，我们考虑元素个数是『奇数和偶数』的临界</span>
        <span class="token comment">//所以我们选择Left&lt;Right</span>
        <span class="token comment">//这样，当Left=Right的时候就算终止条件</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">int</span> mid<span class="token operator">=</span><span class="token punctuation">(</span> Right<span class="token operator">-</span>Left <span class="token punctuation">)</span><span class="token operator">/</span><span class="token number">2</span><span class="token operator">+</span>Left<span class="token punctuation">;</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span><span class="token operator">==</span>target <span class="token punctuation">)</span> 
            <span class="token punctuation">{</span>
                <span class="token keyword">return</span> mid<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            
            
            <span class="token comment">//『易错点，比如1,3中找3，那么nums[left]就等于了nums[mid]</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token operator">&lt;=</span>nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//情况1，左边单调，右边是子问题</span>
                <span class="token comment">//如果target落在左边就很好处理了，继续左边区间搜索</span>
                <span class="token comment">////『易错点』，nums[left]==target可能，比如</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token operator">&lt;=</span>target <span class="token operator">&amp;&amp;</span> target<span class="token operator">&lt;</span>nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span> <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    Right<span class="token operator">=</span>mid<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                <span class="token keyword">else</span>
                <span class="token punctuation">{</span>
                    <span class="token comment">//否则只能去右边无序区间搜索了</span>
                    Left<span class="token operator">=</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span><span class="token comment">//『易错点』</span>
            <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span><span class="token operator">&lt;=</span>nums<span class="token punctuation">[</span>Right<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//情况2，右边单调，左边是子问题</span>
                <span class="token comment">//如果target落在右边区间就很好了，去右边搜索</span>
                <span class="token comment">////『易错点』，nums[Right]==target可能，比如</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span> nums<span class="token punctuation">[</span>mid<span class="token punctuation">]</span><span class="token operator">&lt;</span>target <span class="token operator">&amp;&amp;</span> target<span class="token operator">&lt;=</span>nums<span class="token punctuation">[</span>Right<span class="token punctuation">]</span><span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    Left<span class="token operator">=</span>mid<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                <span class="token keyword">else</span>
                <span class="token punctuation">{</span>
                    <span class="token comment">//否则只能去左边的无序区间搜索了</span>
                    Right<span class="token operator">=</span>mid<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
            
        <span class="token punctuation">}</span>
        
        <span class="token keyword">return</span> <span class="token punctuation">(</span>nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token operator">==</span>target<span class="token punctuation">)</span><span class="token operator">?</span> Left <span class="token operator">:</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br></div></div><h2 id="_02-将字符串转化为整数"><a href="#_02-将字符串转化为整数" class="header-anchor">#</a> 02.将字符串转化为整数</h2> <ul><li>NC100将字符串转化为整数</li> <li>Leetcode<a href="https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/" target="_blank" rel="noopener noreferrer">剑指 Offer 20. 表示数值的字符串<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li></ul> <p>『卡过』</p> <h2 id="_03-字符串分割"><a href="#_03-字符串分割" class="header-anchor">#</a> 03.字符串分割</h2> <p>实现一个字符串分割功能的函数。包含2个辅入参数，1个输出参数，名称及格式自定。</p> <ul><li><p><code>ret split(arg 1 , arg 2);</code></p></li> <li><p><code>arg1:原始字符串，例如&quot;aa;;bb;;;ccc;;;;d;;&quot;</code></p></li> <li><p><code>arg2:分割字符串，如果指定&quot;;;&quot;为分割字符串</code></p></li> <li><p>ret:用于存放每个被分割字符串的容器,该例可将原始字符串分割成<code>[ &quot;aa”,&quot;bb”,&quot;;ccc” ,&quot;&quot;, &quot;d&quot;,&quot;&quot;]</code>六个部分</p></li> <li><p>在main函数中使用以上例子以传参的方式调用该函数，得到正确的分割结果，然后将结果容器中的内容依次换行打印出来。</p></li> <li><p>注意:当分割字符串连续出现时会分割出空字符串，需要考虑当分割字符串出现在头尾时的情况，</p></li> <li><p>在实现算法的过程中尽量不要使用现成的函数。要求在20分钟内成功编译运行该示例.</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>

<span class="token comment">//第1步，设计样例</span>
<span class="token comment">//;;</span>
<span class="token comment">//`;;`//特判</span>
<span class="token comment">//` ;;`</span>
<span class="token comment">//`;; `</span>
<span class="token comment">//;;;</span>

<span class="token comment">//第2步，总体如何『尺取』</span>
<span class="token comment">//第3步，考虑特殊样例</span>

vector<span class="token operator">&lt;</span>string<span class="token operator">&gt;</span> <span class="token function">split</span><span class="token punctuation">(</span> string target<span class="token punctuation">,</span> string useSplit <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
	vector<span class="token operator">&lt;</span>string<span class="token operator">&gt;</span> res<span class="token punctuation">;</span>

	<span class="token comment">//比如;;</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> target<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">==</span>useSplit<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&amp;&amp;</span> target<span class="token operator">==</span>useSplit <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		string temp<span class="token punctuation">;</span>
		res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp <span class="token punctuation">)</span><span class="token punctuation">;</span>
		res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token keyword">int</span> LastPos<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">int</span> cur<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>
	<span class="token keyword">while</span><span class="token punctuation">(</span> string<span class="token operator">::</span>npos<span class="token operator">!=</span>target<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span> useSplit<span class="token punctuation">,</span> LastPos<span class="token punctuation">)</span>  <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		cur<span class="token operator">=</span>target<span class="token punctuation">.</span><span class="token function">find</span><span class="token punctuation">(</span> useSplit<span class="token punctuation">,</span> LastPos <span class="token punctuation">)</span><span class="token punctuation">;</span>
		res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> target<span class="token punctuation">.</span><span class="token function">substr</span><span class="token punctuation">(</span>LastPos<span class="token punctuation">,</span>cur<span class="token operator">-</span>LastPos <span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
		LastPos<span class="token operator">=</span>cur<span class="token operator">+</span>useSplit<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
		<span class="token keyword">if</span><span class="token punctuation">(</span> LastPos<span class="token operator">==</span>target<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>	<span class="token keyword">break</span><span class="token punctuation">;</span>
	<span class="token punctuation">}</span>

	<span class="token comment">//记得抹掉尾巴</span>
	<span class="token keyword">if</span><span class="token punctuation">(</span> LastPos<span class="token operator">==</span>target<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
	<span class="token punctuation">{</span>
		string temp<span class="token punctuation">;</span>
		res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> temp <span class="token punctuation">)</span><span class="token punctuation">;</span>	<span class="token comment">//比如 ;;</span>
	<span class="token punctuation">}</span>
	<span class="token keyword">else</span>
	<span class="token punctuation">{</span>
		res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span> target<span class="token punctuation">.</span><span class="token function">substr</span><span class="token punctuation">(</span>LastPos<span class="token punctuation">,</span>target<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span>LastPos<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> 
	<span class="token punctuation">}</span>

	<span class="token keyword">return</span> res<span class="token punctuation">;</span>

<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    string first<span class="token punctuation">,</span>second<span class="token punctuation">;</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span> cin<span class="token operator">&gt;&gt;</span>first<span class="token operator">&gt;&gt;</span>second <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        vector<span class="token operator">&lt;</span>string<span class="token operator">&gt;</span> res<span class="token operator">=</span><span class="token function">split</span><span class="token punctuation">(</span> first<span class="token punctuation">,</span> second <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span> <span class="token keyword">auto</span> vec <span class="token operator">:</span> res <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//前面输出size是为了告知，比如空的的情况</span>
            <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;size=%d  char==%s\n&quot;</span><span class="token punctuation">,</span> vec<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> vec<span class="token punctuation">.</span><span class="token function">c_str</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>

	<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br></div></div><h3 id="面试题整理"><a href="#面试题整理" class="header-anchor">#</a> 面试题整理</h3> <ul><li>需要严肃说明的是:面试题库作为帮助同学准备面试的辅助资料，但是绝对不能作为备考唯一途径</li> <li>因为面试是一个考察真实水平的，不是背会了答案就可以的，需要你透彻理解的，否则追问问题答不出来反而减分，毕竟技术面试中面试官最痛恨的就是背答案这个事情了。</li></ul> <blockquote><p>但是面试中必考的点且占比非常大的有c基础和算法。</p> <ul><li>决定你是否能拿sp offer（高薪offer）以及是否进名企的是项目和算法。</li></ul></blockquote> <h3 id="操作系统"><a href="#操作系统" class="header-anchor">#</a> 操作系统</h3> <h4 id="_1、请你说一下进程与线程的概念，以及为什么要有进程线程，其中有什么区别，他们各自又是怎么同步的"><a href="#_1、请你说一下进程与线程的概念，以及为什么要有进程线程，其中有什么区别，他们各自又是怎么同步的" class="header-anchor">#</a> 1、请你说一下进程与线程的概念，以及为什么要有进程线程，其中有什么区别，他们各自又是怎么同步的</h4> <blockquote><p>概念：</p></blockquote> <ul><li>进程是对运行时程序的封装，是系统进行<strong>资源调度和分配</strong>的的基本单位，实现了<strong>操作系统的并发</strong>;</li> <li>线程是进程的子任务，是<strong>CPU调度和分派</strong>的基本单位，用于保证程序的实时性，实现<strong>进程内部的并发</strong>;
<ul><li>线程是操作系统可识别的最小执行和调度单位.每个线程都独自占用一个虚拟处理器:独自的寄存器组，指令计数器和处理器状态。每个线程完成不同的任务，但是共享同一地址空间(也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源。</li></ul></li></ul> <blockquote><p>区别：</p></blockquote> <p>1.一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。
⒉.进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。(资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量),数据段（全局变量和静态变量)，扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫<strong>运行时段</strong>，用来存放所有局部变量和临时变量。
3.进程是资源分配的最小单位，线程是CPU调度的最小单位;
4.系统开销:</p> <ul><li>由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/ o设备等。因此，操作系统所付出的开销将显著地大于在创建或撤消线程时的开销。类似地，在进行进程切换时,涉及到整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置。而线程切换只须保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。可见，进程切换的开销也远大于线程切换的开销。</li></ul> <p>5.通信:</p> <ul><li>由于同一进程中的多个线程具有相同的地址空间，致使它们之间的同步和通信的实现，也变得比较容易。进程间通信IPC，线程间可以直接读写进程数据段（如全局变量〉来进行通信――需要进程同步和互斥手段的辅助，以保证数据的一致性。在<strong>有的系统中，线程的切换、同步和通信都无须操作系统内核的干预</strong></li></ul> <p>6.调试：</p> <ul><li>进程编程调试简单可靠性高，但是创建销毁开销大;线程正相反，开销小，切换速度快，但是编程调试相对复杂。</li></ul> <p>7.进程间不会相互影响﹔;线程一个线程挂掉将导致整个进程挂掉</p> <p>8.进程适应于多核、多机分布;线程适用于多核</p> <blockquote><p>进程间同步方式：</p></blockquote> <h3 id="数据结构和算法"><a href="#数据结构和算法" class="header-anchor">#</a> 数据结构和算法</h3> <p>堆和栈</p> <h4 id="请说一说你理解的stack-overflow（栈溢出），并且举个例子导致栈溢出"><a href="#请说一说你理解的stack-overflow（栈溢出），并且举个例子导致栈溢出" class="header-anchor">#</a> 请说一说你理解的stack overflow（栈溢出），并且举个例子导致栈溢出</h4> <ul><li>栈溢出：指的是程序向stack中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致stack中与其相邻的变量的值被改变</li></ul> <blockquote><p>stack overflow产生的原因是：</p></blockquote> <ul><li>1、局部数据</li></ul> <div class="language-c line-numbers-mode"><pre class="language-c"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;stdio.h&gt;</span></span>
<span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;string.h&gt;</span></span>
<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span> <span class="token keyword">int</span> argc<span class="token punctuation">,</span> <span class="token keyword">char</span> <span class="token operator">*</span> argv<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    <span class="token keyword">char</span> buf<span class="token punctuation">[</span><span class="token number">256</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
    <span class="token function">strcpy</span><span class="token punctuation">(</span> buf<span class="token punctuation">,</span> argv<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//这一行，发生了缓冲区溢出错误，因为『源缓冲区』内容是用户输入的</span>
    <span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">&quot;Input:%s\n&quot;</span><span class="token punctuation">,</span>buf<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br></div></div><h2 id="_04-kmp"><a href="#_04-kmp" class="header-anchor">#</a> 04.KMP</h2> <ul><li><p><a href="https://www.nowcoder.com/practice/bb1615c381cc4237919d1aa448083bcc?tpId=190&&tqId=37993&rp=1&ru=/activity/oj&qru=/ta/job-code-high-rd/question-ranking" target="_blank" rel="noopener noreferrer">KMP算法<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></p></li> <li><p><a href="https://zhuanlan.zhihu.com/p/265167678" target="_blank" rel="noopener noreferrer">Carl学长<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a>的</p></li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token macro property"><span class="token directive-hash">#</span><span class="token directive keyword">include</span><span class="token string">&lt;bits/stdc++.h&gt;</span></span>
<span class="token keyword">using</span> <span class="token keyword">namespace</span> std<span class="token punctuation">;</span>


<span class="token keyword">class</span> <span class="token class-name">KMP</span>
<span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">void</span> <span class="token function">getNext</span><span class="token punctuation">(</span> vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token operator">&amp;</span> next<span class="token punctuation">,</span> string s <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token comment">//我的理解，getNext其实本质也是个strStr的函数，</span>
        <span class="token comment">//其中，文本串是『后缀XXX』，needle__也就是s是『前缀XXX』</span>

        <span class="token keyword">int</span> prefixPos<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//初始化『前缀末尾位置』</span>
        next<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//初始化next[0]的回退位置</span>

        <span class="token comment">//i意义1：表示『后缀末尾的位置』,初始化next[i]</span>
        <span class="token comment">//意义2：此外，i还代表当前XXX</span>
        <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> suffixPos <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> suffixPos <span class="token operator">&lt;</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>suffixPos<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>

            <span class="token comment">//易错，不能是if，因为可能借助next多次回退</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> prefixPos<span class="token operator">&gt;</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> s<span class="token punctuation">[</span>prefixPos<span class="token punctuation">]</span><span class="token operator">!=</span>s<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                prefixPos<span class="token operator">=</span>next<span class="token punctuation">[</span>prefixPos<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token keyword">if</span><span class="token punctuation">(</span> s<span class="token punctuation">[</span>prefixPos<span class="token punctuation">]</span><span class="token operator">==</span>s<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>prefixPos<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//初始化next</span>
            next<span class="token punctuation">[</span>suffixPos<span class="token punctuation">]</span><span class="token operator">=</span>prefixPos<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

    <span class="token punctuation">}</span>


    <span class="token keyword">int</span> <span class="token function">strStr</span><span class="token punctuation">(</span> string haystack<span class="token punctuation">,</span> string needle <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token operator">==</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span> <span class="token function">next</span><span class="token punctuation">(</span> needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">getNext</span><span class="token punctuation">(</span> next<span class="token punctuation">,</span> needle <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token keyword">int</span> j<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span><span class="token comment">//needle串，当前需要测试匹配性的位置</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>haystack<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token comment">//易错：不能用if，因为可能多次借助next数组回退</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> j<span class="token operator">&gt;</span><span class="token number">0</span> <span class="token operator">&amp;&amp;</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">!=</span>needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                j<span class="token operator">=</span>next<span class="token punctuation">[</span>j<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//如果匹配了1个字符，显然会后移</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> haystack<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>needle<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token operator">++</span>j<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>

            <span class="token comment">//完全匹配</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> j<span class="token operator">==</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token comment">//注意，因为i还来不及+1，所以，返回前要+1然后才能减掉</span>
                <span class="token keyword">return</span> <span class="token punctuation">(</span> i<span class="token operator">+</span><span class="token number">1</span><span class="token operator">-</span>needle<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span><span class="token comment">//匹配失败</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">int</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>

    <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br><span class="line-number">54</span><br><span class="line-number">55</span><br><span class="line-number">56</span><br><span class="line-number">57</span><br><span class="line-number">58</span><br><span class="line-number">59</span><br><span class="line-number">60</span><br><span class="line-number">61</span><br><span class="line-number">62</span><br><span class="line-number">63</span><br><span class="line-number">64</span><br><span class="line-number">65</span><br><span class="line-number">66</span><br><span class="line-number">67</span><br><span class="line-number">68</span><br><span class="line-number">69</span><br><span class="line-number">70</span><br><span class="line-number">71</span><br><span class="line-number">72</span><br><span class="line-number">73</span><br><span class="line-number">74</span><br><span class="line-number">75</span><br><span class="line-number">76</span><br><span class="line-number">77</span><br><span class="line-number">78</span><br><span class="line-number">79</span><br><span class="line-number">80</span><br></div></div><h2 id="_05-⭐️二叉树中的最大路径和『树形dp』"><a href="#_05-⭐️二叉树中的最大路径和『树形dp』" class="header-anchor">#</a> 05.⭐️二叉树中的最大路径和『树形dp』</h2> <ul><li><a href="https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/" target="_blank" rel="noopener noreferrer">124. 二叉树中的最大路径和<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>本题是<a href="https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/shu-xing-dpfu-tong-lei-wen-ti-by-liweiwe-wupz/" target="_blank" rel="noopener noreferrer">树形 DP、后序遍历<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>『使用后序遍历的原因』
<ul><li>前序遍历——深度优先遍历就是从根结点开始在树中转一圈，最后回到根结点。</li> <li>我们采用<strong>后序遍历</strong>计算结果的方式，表现为：从叶子结点开始，一层一层向上传递信息，最后在根结点汇总结果。</li> <li>为什么是「后序遍历」呢？
<ul><li>因为二叉树从子结点到父结点只会有一条路径；</li> <li>而从根结点到子节点至多会有两条路径。</li></ul></li> <li>「后序遍历」相当于 <strong>先求得两个子问题的结果，再根据两个子问题的结果得到当前规模更大的子问题的结果</strong>，这是「分而治之」的思想。</li></ul></li> <li>「树形 DP」与的状态设计与状态转移是<strong>隐含在递归</strong>方法里的，这一点请大家留意。</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token comment">/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */</span>
<span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> res<span class="token punctuation">;</span>
    <span class="token comment">//获得当前节点，（左边or右边）+cur.val的，这一单支脉的『和』get</span>
    <span class="token comment">//显然，最终问题就转换为：路径和=getLeft+getRight+Cur.val</span>
    <span class="token keyword">int</span> <span class="token function">getCurNodeLeftOrRightDepthSum</span><span class="token punctuation">(</span> TreeNode <span class="token operator">*</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token comment">//注意，之所以选择max(0)去比，因为Node.val如果&lt;0，那我还不如不选这个分支</span>
        <span class="token keyword">int</span> LeftVal<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token function">getCurNodeLeftOrRightDepthSum</span><span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>left<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> Rightval<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token function">getCurNodeLeftOrRightDepthSum</span><span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>right<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//注意：root-&gt;val牵头的单支脉，所以，就算自己&lt;0，也得加</span>
        <span class="token keyword">return</span> root<span class="token operator">-&gt;</span>val <span class="token operator">+</span> <span class="token function">max</span><span class="token punctuation">(</span> LeftVal<span class="token punctuation">,</span> Rightval <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">int</span> <span class="token function">solve</span><span class="token punctuation">(</span> TreeNode <span class="token operator">*</span>root <span class="token punctuation">)</span>
    <span class="token punctuation">{</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token keyword">nullptr</span><span class="token operator">==</span>root <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">int</span> LeftVal<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token function">solve</span><span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>left<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> Rightval<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token function">solve</span><span class="token punctuation">(</span>root<span class="token operator">-&gt;</span>right<span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>

        <span class="token comment">//这是dp的地方，总归有一个牵头节点，正好</span>
        res<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> res<span class="token punctuation">,</span> root<span class="token operator">-&gt;</span>val<span class="token operator">+</span> LeftVal <span class="token operator">+</span>Rightval <span class="token punctuation">)</span><span class="token punctuation">;</span>
        
        <span class="token keyword">return</span> root<span class="token operator">-&gt;</span>val <span class="token operator">+</span> <span class="token function">max</span><span class="token punctuation">(</span> LeftVal<span class="token punctuation">,</span> Rightval <span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>

    <span class="token keyword">int</span> <span class="token function">maxPathSum</span><span class="token punctuation">(</span>TreeNode<span class="token operator">*</span> root<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        res<span class="token operator">=</span>INT_MIN<span class="token punctuation">;</span>
        <span class="token function">solve</span><span class="token punctuation">(</span> root <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br><span class="line-number">36</span><br><span class="line-number">37</span><br><span class="line-number">38</span><br><span class="line-number">39</span><br><span class="line-number">40</span><br><span class="line-number">41</span><br><span class="line-number">42</span><br><span class="line-number">43</span><br><span class="line-number">44</span><br><span class="line-number">45</span><br><span class="line-number">46</span><br><span class="line-number">47</span><br><span class="line-number">48</span><br><span class="line-number">49</span><br><span class="line-number">50</span><br><span class="line-number">51</span><br><span class="line-number">52</span><br><span class="line-number">53</span><br></div></div><h2 id="_06-最接近的三数之和"><a href="#_06-最接近的三数之和" class="header-anchor">#</a> 06.最接近的三数之和</h2> <ul><li><a href="https://leetcode-cn.com/problems/3sum-closest/" target="_blank" rel="noopener noreferrer">16. 最接近的三数之和<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>双指针</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> <span class="token function">threeSumClosest</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> target<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">sort</span><span class="token punctuation">(</span> nums<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> nums<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">int</span> res<span class="token operator">=</span>nums<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token operator">+</span>nums<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token operator">+</span>nums<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">&lt;</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">int</span> Left<span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span>Right<span class="token operator">=</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
            <span class="token keyword">while</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                <span class="token keyword">int</span> sum<span class="token operator">=</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">+</span>nums<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token operator">+</span>nums<span class="token punctuation">[</span>Right<span class="token punctuation">]</span><span class="token punctuation">;</span>
                <span class="token comment">//更新res</span>
                <span class="token keyword">if</span><span class="token punctuation">(</span> <span class="token function">abs</span><span class="token punctuation">(</span>sum<span class="token operator">-</span>target<span class="token punctuation">)</span><span class="token operator">&lt;</span> <span class="token function">abs</span><span class="token punctuation">(</span>res<span class="token operator">-</span>target<span class="token punctuation">)</span> <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    res<span class="token operator">=</span>sum<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>

                <span class="token keyword">if</span><span class="token punctuation">(</span> sum<span class="token operator">==</span>target <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    <span class="token keyword">return</span> target<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                <span class="token keyword">else</span> <span class="token keyword">if</span><span class="token punctuation">(</span> sum<span class="token operator">&gt;</span>target <span class="token punctuation">)</span>
                <span class="token punctuation">{</span>
                    <span class="token operator">--</span>Right<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
                <span class="token keyword">else</span>
                <span class="token punctuation">{</span>
                    <span class="token operator">++</span>Left<span class="token punctuation">;</span>
                <span class="token punctuation">}</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br><span class="line-number">24</span><br><span class="line-number">25</span><br><span class="line-number">26</span><br><span class="line-number">27</span><br><span class="line-number">28</span><br><span class="line-number">29</span><br><span class="line-number">30</span><br><span class="line-number">31</span><br><span class="line-number">32</span><br><span class="line-number">33</span><br><span class="line-number">34</span><br><span class="line-number">35</span><br></div></div><h3 id="同类问题"><a href="#同类问题" class="header-anchor">#</a> 同类问题</h3> <p>这些问题依然是先理解题目中「直径」「路径」的定义，有些问题「路径」指的是结点的个数，有些问题「路径」指的是边的条数。</p> <p>「力扣」第 124 题：二叉树中的最大路径和（困难，本节讲解问题）；
「力扣」第 337 题：打家劫舍 III（中等）；
「力扣」第 543 题：二叉树的直径（简单）；
「力扣」第 687 题：最长同值路径（中等）；
「力扣」第 968 题：监控二叉树（困难）；
「力扣」第 1372 题：二叉树中的最长交错路径（中等）；</p> <h2 id="_07-盛最多水的容器"><a href="#_07-盛最多水的容器" class="header-anchor">#</a> 07.盛最多水的容器</h2> <ul><li><a href="https://leetcode-cn.com/problems/container-with-most-water/" target="_blank" rel="noopener noreferrer">11. 盛最多水的容器<svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg></a></li> <li>优雅的双指针题目</li></ul> <div class="language-cpp line-numbers-mode"><pre class="language-cpp"><code><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span><span class="token operator">:</span>
    <span class="token keyword">int</span> <span class="token function">maxArea</span><span class="token punctuation">(</span>vector<span class="token operator">&lt;</span><span class="token keyword">int</span><span class="token operator">&gt;</span><span class="token operator">&amp;</span> height<span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token keyword">int</span> res<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>

        <span class="token keyword">int</span> Left<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span>Right<span class="token operator">=</span>height<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span>
        <span class="token keyword">while</span><span class="token punctuation">(</span> Left<span class="token operator">&lt;</span>Right <span class="token punctuation">)</span>
        <span class="token punctuation">{</span>
            <span class="token keyword">if</span><span class="token punctuation">(</span> height<span class="token punctuation">[</span>Left<span class="token punctuation">]</span><span class="token operator">&lt;</span>height<span class="token punctuation">[</span>Right<span class="token punctuation">]</span> <span class="token punctuation">)</span>
            <span class="token punctuation">{</span>
                res<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> res<span class="token punctuation">,</span> <span class="token punctuation">(</span>Right<span class="token operator">-</span>Left<span class="token punctuation">)</span><span class="token operator">*</span>height<span class="token punctuation">[</span>Left<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">++</span>Left<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
            <span class="token keyword">else</span>
            <span class="token punctuation">{</span>
                res<span class="token operator">=</span><span class="token function">max</span><span class="token punctuation">(</span> res<span class="token punctuation">,</span> <span class="token punctuation">(</span>Right<span class="token operator">-</span>Left<span class="token punctuation">)</span><span class="token operator">*</span>height<span class="token punctuation">[</span>Right<span class="token punctuation">]</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
                <span class="token operator">--</span>Right<span class="token punctuation">;</span>
            <span class="token punctuation">}</span>
        <span class="token punctuation">}</span>

        <span class="token keyword">return</span> res<span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre> <div class="line-numbers-wrapper"><span class="line-number">1</span><br><span class="line-number">2</span><br><span class="line-number">3</span><br><span class="line-number">4</span><br><span class="line-number">5</span><br><span class="line-number">6</span><br><span class="line-number">7</span><br><span class="line-number">8</span><br><span class="line-number">9</span><br><span class="line-number">10</span><br><span class="line-number">11</span><br><span class="line-number">12</span><br><span class="line-number">13</span><br><span class="line-number">14</span><br><span class="line-number">15</span><br><span class="line-number">16</span><br><span class="line-number">17</span><br><span class="line-number">18</span><br><span class="line-number">19</span><br><span class="line-number">20</span><br><span class="line-number">21</span><br><span class="line-number">22</span><br><span class="line-number">23</span><br></div></div><ul><li>环形链表的约瑟夫问题</li></ul> <p>这题的数学解法，还是剑指offer上的写的比《具体数学》上面的好</p></div> <div class="page-edit"><!----> <!----></div> <!----> </div> <!----></div></div>
    <script src="/assets/js/app.c70e21ad.js" defer></script><script src="/assets/js/9.3813842d.js" defer></script>
  </body>
</html>
